package com.tgy.programmer_code_interview_guide._02_linkedList;

/**
 * @Author: tgy
 * @Date: 1/23/21 9:44 AM
 */
public class _04_翻转链表 {

    public static Node reversal(Node root) {

        if (root == null || root.next == null) {

            return root;
        }

        Node preNode = null,curNode = root, nextNode = null;

        while (curNode != null) {
            // 保存next，因为next要用preNode赋值
            nextNode = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }

        return preNode;
    }

    public static  Node recursionReversal(Node node) {

        if (node == null || node.next == null) {

            return node;
        }

        Node nextNode = node.next;
        Node root = recursionReversal(nextNode);
        nextNode.next = node;
        node.next = null;
        return root;
    }

    public static void main(String[] args) {

        Node root = new Node(1);
        root.next = new Node(2);
        root.next.next = new Node(3);
        root.next.next.next = new Node(4);
        root.next.next.next.next = new Node(5);

        root = recursionReversal(root);

        Nodes.printNode(root);
    }
}
